TXL solution to TIL Chairmarks #4.5: Static slicing. This example implements backward static slicing using cascaded markup to a fixed point.

Notes: In an implementation for a real scoped language, a unique renaming transformation would normally be done before slicing in order to remove ambiguities of reference. Alias resolution may or may not be necessary depending on the language. Inter-procedural slicing is added in the usual way, by marking the formal parameters corresponding to any argument variable of the slice passed by reference to the procedure.

-- JamesCordy - 02 Mar 2007

File "TILbackslice.Txl"

% Backward static slicing of Tiny Imperative Language programs
% Jim Cordy, February 2007

% Given a TIL program with a single statement marked up using the
% XML markup <mark> </mark>, backward slices the program from that
% statement and its referenced variables.

% Works by inducing markup of unmarked statements from already marked-up
% statements beginning with the original marked statement until a fixed 
% point is reached, then removing all remaining unmarked statements.
% No dependency graph is required.

% Begin with the TIL base grammar
include "TIL.Grm"

% Add allowance for XML markup of TIL statements
redefine statement
        ...
    |   [marked_statement]
end redefine

define marked_statement
            [xmltag] [statement] [xmlend]
end define

define xmltag
        < [SPOFF] [id] > [SPON]
end define

define xmlend
        < [SPOFF] / [id] > [SPON]
end define

% Conflate while and for statements into one form to optimize
% handling of both forms in one rule
redefine statement
        [loop_statement]
    |   ...
end redefine

define loop_statement
        [loop_head]                [NL][IN]
            [statement*]           [EX]
        'end                       [NL]
end define

define loop_head
        while [expression] do
    |   for [id] := [expression] to [expression] do
end define


% The main function gathers the steps of the transformation:
% induce markup to a fixed point, remove unmarked statements,
% remove declarations for variables not used in the slice,
% and strip the markups to yield the sliced program

function main
    replace [program]
        P [program]
    by
        P [propogateMarkupToFixedPoint]
          [removeUnmarkedStatements]
          [removeRedundantDeclarations]
          [stripMarkup]
end function

% Back propogate markup of statements beginning with the initially
% marked statement of interest.  Continue until a fixed point, 
% when no new markups are induced

rule propogateMarkupToFixedPoint
    replace [program]
        P [program]

    construct NP [program]
        P [backPropogateAssignments]
          [backPropogateReads]
          [whilePropogateControlVariables]
          [loopPropogateMarkup]
          [loopPropogateMarkupIn]
          [ifPropogateMarkupIn]
          [compoundPropogateMarkupOut]

    % We're at a fixed point when P = NP   :-)
    deconstruct not NP
        P
    by
        NP 
end rule

% Rule to back-propogate markup of assignments.
% A previous assignment is in the slice if its assigned 
% variable is used in a following marked statement

rule backPropogateAssignments
    skipping [marked_statement]
    replace [statement*]
        X [id] := E [expression] ; 
        More [statement*]
    where 
        More [hasMarkedUse X]
    by
        <mark> X := E; </mark>
        More 
end rule

% Similar rule for back-propogating markup of read statements

rule backPropogateReads
    skipping [marked_statement]
    replace [statement*]
        read X [id] ; 
        More [statement*]
    where 
        More [hasMarkedUse X]
    by
        <mark> read X; </mark>
        More 
end rule

function hasMarkedUse X [id]
    match * [marked_statement]
        M [marked_statement]
    deconstruct * [expression] M
        E [expression]
    deconstruct * [id] E
        X
end function

% Assignments to variables inside a while loop containing statements
% of a slice are also in the slice if the while condition uses them

rule whilePropogateControlVariables
    replace $ [statement]
        while E [expression] do
            S [statement*]
        'end
    deconstruct * [statement] S
        _ [marked_statement]
    by
        while E do
            S [markAssignmentsTo E]
              [markReadsOf E]
        'end
end rule

rule markAssignmentsTo Exp [expression]
    skipping [marked_statement]
    replace $ [statement]
        X [id] := E [expression] ;
    deconstruct * [id] Exp
        X
    by
        <mark> X := E; </mark>
end rule

rule markReadsOf Exp [expression]
    skipping [marked_statement]
    replace $ [statement]
        read X [id] ;
    deconstruct * [id] Exp
        X
    by
        <mark> read X; </mark>
end rule

% Rule for propagating dependencies around loops.
% An assignment inside a loop is in the slice if its assigned variable
% is used in a marked statement anywhere inside the loop

rule loopPropogateMarkup
    replace $ [statement]
        Head [loop_head]
            S [statement*]
        'end
    construct MarkedS [marked_statement*]
        _ [^ S]
    construct MarkedE [expression*]
        _ [^ MarkedS]
    by
        Head
            S [markAssignmentsTo each MarkedE]
              [markReadsOf each MarkedE]
        'end
end rule

% Rule for propagating dependencies into loops.
% An assignment inside the loop is in the slice if its assigned variable 
% is used in a marked statement anywhere following the loop

rule loopPropogateMarkupIn
    replace $ [statement*]
        Head [loop_head]
            S [statement*]
        'end
        MoreS [statement*]
    construct MarkedMoreS [marked_statement*]
        _ [^ MoreS]
    construct MarkedMoreE [expression*]
        _ [^ MarkedMoreS]
    by
        Head
            S [markAssignmentsTo each MarkedMoreE]
              [markReadsOf each MarkedMoreE]
        'end
        MoreS
end rule

% Rule for propagating dependencies into if statements.
% An assignment inside the then or else part of the if is in the slice 
% if its assigned variable is used in a marked statement anywhere 
% following the if

rule ifPropogateMarkupIn
    replace $ [statement*]
        if E [expression] then
            ST [statement*]
        ElseSE [opt else_statement]
        'end
        MoreS [statement*]
    construct MarkedMoreS [marked_statement*]
        _ [^ MoreS]
    construct MarkedMoreE [expression*]
        _ [^ MarkedMoreS]
    by
        if E then
            ST [markAssignmentsTo each MarkedMoreE]
        ElseSE [markAssignmentsTo each MarkedMoreE]
        'end
        MoreS
end rule

% Rule for propagating dependencies out.
% A compound statement of any kind is in the loop if it contains
% a marked statement

rule compoundPropogateMarkupOut
    replace $ [statement*]
        CS [statement]
        More [statement*]
    deconstruct not CS
        _ [marked_statement]
    deconstruct * [statement] CS
        _ [marked_statement]
    by
        <mark> CS </mark>
        More
end rule

% Rule to remove all unmarked statements after the fixed point
% is reached, yielding only the slice

rule removeUnmarkedStatements
    replace [statement*]
        S [statement]
        More [statement*]
    deconstruct not S
        _ [marked_statement]
    deconstruct not S
        _ [declaration]
    by
        More
end rule

% Rule to remove declarations not needed in the slice

rule removeRedundantDeclarations
    replace [statement*]
        var X [id] ;
        More [statement*]
    deconstruct not * [id] More
        X
    by
        More
end rule

% Rule to strip all markup when we're done

rule stripMarkup
    replace [statement]
        < _ [id] > S [statement] </ _ [id] >
    by
        S
end rule

Example run 1:

<linux> cat sliceg1.til
var n;
read n;
var fac;
fac := 1;
var sum;
sum := 0;
var i;
i := 1;
while i != n+1 do
    fac := fac * i;
    sum := sum + i;
    i := i + 1;
end
<foo>write fac;</foo>
write sum;

<linux> txl sliceg1.til TILbackslice.Txl
TXL v10.4d (4.2.07) (c)1988-2007 Queen's University at Kingston
Compiling TILbackslice.Txl ... 
Parsing sliceg1.til ...
Transforming ...
var n;
read n;
var fac;
fac := 1;
var i;
i := 1;
while i != n + 1 do
    fac := fac * i;
    i := i + 1;
end
write fac;

<linux>

Example run 2:

<linux> cat sliceg2.til 
var x;
x := 0;
var t;
t := 0;
for i := 1 to 10 do
    if x = 1 then
        t := t * i;
    else
        t := t + i;
    end
    x := 1;
end
<mark>write x;</mark>

<linux> txl sliceg2.til TILbackslice.Txl
TXL v10.4d (4.2.07) (c)1988-2007 Queen's University at Kingston
Compiling TILbackslice.Txl ... 
Parsing sliceg2.til ...
Transforming ...
var x;
x := 0;
for i := 1 to 10 do
    x := 1;
end
write x;

<linux> 

Example run 3:

<linux> cat sliceg6.til
var lines;
lines := 0;    
var chars;    
var n;    
read n;
var eof_flag;
read eof_flag;
chars := n;   
while eof_flag do
    lines := lines + 1;     
    read n;
    read eof_flag;
    chars := chars + n;   
end
<mark>write (lines);</mark>
write (chars);

<linux> txl sliceg6.til TILbackslice.Txl
TXL v10.4d (4.2.07) (c)1988-2007 Queen's University at Kingston
Compiling TILbackslice.Txl ... 
Parsing sliceg6.til ...
Transforming ...
var lines;
lines := 0;
var eof_flag;
read eof_flag;
while eof_flag do
    lines := lines + 1;
    read eof_flag;
end
write (lines);

<linux>

-- JamesCordy - 02 Mar 2007

TXL solution to TIL Chairmarks #3.2, Common subexpression elimination.

Thie simple example demonstrates the basics of common subexpression elimination at the statement level using TXL. In a realistic application for optimizing numerical programs, this would be combined with constant folding and code motion transformations to yield a higher quality result.

-- JamesCordy - 19 Oct 2007

File "TILcommonsubexp.Txl"

% TXL transformation to recognize and optimize common subexpressions
% Jim Cordy, March 2007

% This program finds subexpressions that are used two or more times without
% intervening changes to the variables used in it, and introduces a new
% temporary variable to optimize it to a single computation.

% Based on the TIL base grammar
include "TIL.Grm"

% Preserve comments, we're probably going to maintain the result
include "TILCommentOverrides.Grm"

% Override grammar to abstract compound statements
redefine statement
        [compound_statement]
    |   ...
end redefine

define compound_statement
        [if_statement]
    |   [while_statement]
    |   [for_statement]
end define

% Allow statements to be attributed so we don't mistake one we've
% generated for one we need to process

redefine statement 
        ...
    |   [statement] [attr 'NEW]
end redefine

% Main function

function main
    replace [program]
        P [program]
    by
        P [optimizeSubexpressions]
end function

rule optimizeSubexpressions
    replace [statement*]
        S1 [statement]
        SS [statement*]

    % Don't process statements we generated
    deconstruct not * [attr 'NEW] S1
        'NEW

    % What we're looking for is an expression ...
    deconstruct * [expression] S1
        E [expression]

    % ... that is nontrivial ...
    deconstruct * [op]  E
        _ [op]

    % ... and repeated 
    deconstruct * [expression] SS
        E

    % See if we can abstract it (checks if variables assigned between)
    where
        SS [?replaceExpnCopies S1 E 'T]

    % If so, generate a new temporary variable name ...
    construct T [id]
        _ [unquote "temp"] [!]

    % ... declare it, assign it the common expression,
    % and replace instances of the expression with it
    construct NewS [statement*]
        'var T; 'NEW
        T := E; 'NEW
        S1 [replaceExpn E T]
        SS [replaceExpnCopies S1 E T]
    by
        NewS 
end rule

% Recursively replace copies of a given expression with a given temporary variable id,
% provided the variables used in the expression are not assigned in between

function replaceExpnCopies S1 [statement] E [expression] T [id]
    construct Eids [id*]
        _ [^ E]

    % If the previous statement did not assign any of the variables in the expression
    where not
        S1 [assigns each Eids]

    % Then we can continue to substitute the temporary variable for the expression
    % in the next statement ...
    replace [statement*]
        S [statement]
        SS [statement*]

    % ... as long as it isn't a compound statement that internally assigs one of 
    % the variables in the expression 
    where not all
        S [assignsOne Eids]
          [isCompoundStatement]
    by
        S [replaceExpn E T]
        SS [replaceExpnCopies S E T]
end function

% Condition function checking to see if a statement assigns a variable

function assignsOne Eids [id*]
    match [statement]
        S [statement]
    where 
        S [assigns each Eids]
end function

function assigns Id [id]
    match * [statement]
        Id := _ [expression] ;
end function

function isCompoundStatement
    match [statement]
        _ [compound_statement]
end function

rule replaceExpn E [expression] T [id]
    replace [expression]
        E
    by
        T
end rule

Example run: "commonsubexpeg.til" is a meaningless little program with lots of common subexpressions, both optimizable and not.

<linux> cat commonsubexpeg.til 
// Silly TIL example with lots of common subexpressions
var a;
var b;
var c;
a := 1;
b := a + 1;
var i;
i := 7;
c := a + 1;
i := i - c;
c := b + i;
for i := 1 to 10 do
    a := b + i;
    if b + i != 10 then
        c := b;
    else
        c := b + i;
    end
    b := b + i;
end 
while b != 10 do
    a := b + i;
    if b + i != 10 then
        a := c;
    else
        c := b + i;
    end
    b := b + i;
end
write (i - c);

<linux> txl commonsubexpeg.til TILcommonsubexp.Txl 
TXL v10.5 (22.9.07) (c)1988-2007 Queen's University at Kingston
Compiling TILcommonsubexp.Txl ... 
Parsing commonsubexpeg.til ...
Transforming ...

// Silly TIL example with lots of common subexpressions
var a;
var b;
var c;
a := 1;
var temp1;
temp1 := a + 1;
b := temp1;
var i;
i := 7;
c := temp1;
i := i - c;
c := b + i;
for i := 1 to 10 do
    var temp2;
    temp2 := b + i;
    a := temp2;
    if temp2 != 10 then
        c := b;
    else
        c := temp2;
    end
    b := temp2;
end
while b != 10 do
    var temp3;
    temp3 := b + i;
    a := temp3;
    if temp3 != 10 then
        a := c;
    else
        c := temp3;
    end
    b := temp3;
end
write (i - c);

<linux> 

-- JamesCordy - 19 Oct 2007

TXL solution to TIL Chairmarks #4.6: Clone detection with consistent renaming. This example implements clone detection for clones of structured statements (if, while, for) with consistent renaming in a TIL program and outputs both a table of clone classes and the program with clones marked up using XML tags indicating the clone class of each instance.

-- JamesCordy - 16 Oct 2007

File "TILclonesrenamed.Txl"

% Clone detection on Tiny Imperative Language programs
% Jim Cordy, October 2007

% Given a TIL program, this program finds structured statement
% clones that differ only by consistent renaming, and marks them
% up in the source with their clone class.  The clone classes
% themselves are output on the standard error stream as well.

% Usage:  txl program.til TILclonesrenamed.Txl > program.clones 2> program.cloneclasses

% Begin with the TIL base grammar
include "TIL.Grm"

% Overrides to conflate all structured statements into one nonterminal type.
% Putting [structured_statement] before existing statement forms makes
% it the preferred parse for the statements it matches.

redefine statement
        [structured_statement] 
    |   ...
end redefine

define structured_statement
        [if_statement]
    |   [for_statement]
    |   [while_statement]
end define

% Overrides to allow XML markup of TIL statements.

redefine statement
        ...
    |   [marked_statement]
end redefine

define marked_statement
        [xmltag]        [NL][IN] 
            [statement] [EX] 
        [xmlend]        [NL]
end define

% [SPOFF] and [SPON] temporarily disable default spacing in tags

define xmltag
        < [SPOFF] [id] [SP] [id] = [number] > [SPON]
end define

define xmlend
        < [SPOFF] / [id] > [SPON]
end define


% Main program

function main
    replace [program]
        P [program]

    % First make a table of all structured statements that are
    % repeated but for consistent renaming
    construct StructuredClones [repeat structured_statement]
        _ [findStructuredStatementClones P]

    % Now mark up all consistently renamed instances of each of them in the program
    % CloneNumber keeps track of the index of each one in the table as we step 
    % through it using 'each'
    export CloneNumber [number] 0
    by
        P [markCloneInstances each StructuredClones]
end function

% We make a table of the cloned structured statements by first making a table
% of all structured statements in the program, then looking for repeats

function findStructuredStatementClones P [program] 
    % Use the extract [^] function to make a table of all structured statements in the program
    % and normalize them to standard renaming 
    construct StructuredStatements [repeat structured_statement]
            _ [^ P] [renameStructuredStatement]

    % Now add each one that is repeated to the table of clones 
    construct StructuredClones [repeat structured_statement]
        _ [addIfClone StructuredStatements each StructuredStatements]

    % Output the table to the standard error stream as a clone class table
    construct CloneTable [repeat statement]
        _ [addCloneClass 0 StructuredClones]
          [print]

    % Pass the table back to the main function
    replace [repeat structured_statement]
        % empty to begin with
    by
        StructuredClones
end function

function addIfClone StructuredStatements [repeat structured_statement] 
                    Stmt [structured_statement]
    % A structured statement is cloned if it appears twice in the table of all statements
    deconstruct * StructuredStatements
        Stmt
        Rest [repeat structured_statement]
    deconstruct * [structured_statement] Rest
        Stmt

    % If it does appear (at least) twice, add it to the table of clones 
    replace [repeat structured_statement]
        StructuredClones [repeat structured_statement]
    % Make sure it's not already in the table
    deconstruct not * [structured_statement] StructuredClones
        Stmt
    by
        StructuredClones [. Stmt]
end function

% Create a readable version of the clone class table for output

function addCloneClass NM1 [number] Clones [repeat structured_statement]
    % Index of the class in the table of clones
    construct N [number]
        NM1 [+ 1]

    % Get the next clone
    deconstruct Clones
        Clone [structured_statement]
        Rest [repeat structured_statement]

    % Mark up the clone as a numbered clone class
    replace [repeat statement]
        Stmts [repeat statement]
    construct NewStmt [statement]
        <clone_class class=N> 
            Clone 
        </clone_class>
    % And add it to the table to output
    by
        Stmts [. NewStmt] 
              [addCloneClass N Rest]
end function

% Once we have the table of all clones, we mark up each instance of each of them
% in the program with its clone class, that is, the index of it in the clone table

rule markCloneInstances StructuredClone [structured_statement]
    % Keep track of the index of this clone in the table
    import CloneNumber [number]
    export CloneNumber 
        CloneNumber [+ 1]

    % Mark up all instances of it in the program
    % 'skipping' avoids marking any instance twice
    skipping [marked_statement]
    replace [statement]
        Stmt [structured_statement]

    % Normalize to standard renaming for comparison
    construct RenamedStmt [structured_statement]
        Stmt [renameStructuredStatement]

    % If the renamed structured statement is an instance of the clone class ...
    deconstruct RenamedStmt
        StructuredClone
    % ... then mark it as such
    by
        <clone class=CloneNumber> Stmt </clone>
end rule

% Rule to normalize structured statements by consistent renaming of identifiers
% to normal form (x1, x2, x3, ...)

rule renameStructuredStatement
    % For each outer structured statement in the scope
    skipping [structured_statement]
    replace $ [structured_statement]
        Stmt [structured_statement]

    % Make a list of all of the unique identifiers in the statement
    construct Ids [repeat id]
        _ [^ Stmt] [removeDuplicateIds]

    % Make normalized new names of the form xN for each of them
    construct GenIds [repeat id]
        Ids [genIds 0]

    % Consistently replace each instance of each one by its normalized form
    by
        Stmt [$ each Ids GenIds]
end rule

% Utility rule - remove duplicate ids from a list

rule removeDuplicateIds
    replace [repeat id]
        Id [id] Rest [repeat id]
    deconstruct * [id] Rest
        Id
    by
        Rest
end rule

% Utility rule - make a normalized id of the form xN for each unique id in a list

function genIds NM1 [number]
    % For each id in the list
    replace [repeat id]
        _ [id] 
        Rest [repeat id] 

    % Generate the next xN id
    construct N [number]
        NM1 [+ 1]
    construct GenId [id]
        _ [+ 'x] [+ N]

    % Replace the id with the generated one
    % and recursively do the next one
    by
        GenId 
        Rest [genIds N]
end function

Example run 1 (with exact clones):

<linux> cat cloneseg1.til
// Silly meaningless example with lots of exact clones
var n;
write "Input n please";
read n;
var f;
f := 2;
while n != 1 do
    while (n / f) * f = n do
        write f;
        n := n / f;
    end
    if n = 3 then
        n := 2;
    end
    f := f + 1;
end
while (n / f) * f = n do
    write f;
    if n = 3 then
        n := 2;
    end
    n := n / f;
end
while n != 1 do
    while (n / f) * f = n do
        write f;
        n := n / f;
        if n = 3 then
            n := 2;
        end
    end
    f := f + 1;
    while (n / f) * f = n do
        write f;
        n := n / f;
    end
end

<linux> txl cloneseg1.til TILclonesrenamed.Txl
TXL v10.5 (22.9.07) (c)1988-2007 Queen's University at Kingston
Compiling TILclonesrenamed.Txl ... 
Parsing cloneseg1.til ...
Transforming ...

<clone_class class=1>
    while (x1 / x2) * x2 = x1 do
        write x2;
        x1 := x1 / x2;
    end
</clone_class>
<clone_class class=2>
    if x1 = 3 then
        x1 := 2;
    end
</clone_class>

var n;
write "Input n please";
read n;
var f;
f := 2;
while n != 1 do
    <clone class=1>
        while (n / f) * f = n do
            write f;
            n := n / f;
        end
    </clone>
    <clone class=2>
        if n = 3 then
            n := 2;
        end
    </clone>
    f := f + 1;
end
while (n / f) * f = n do
    write f;
    <clone class=2>
        if n = 3 then
            n := 2;
        end
    </clone>
    n := n / f;
end
while n != 1 do
    while (n / f) * f = n do
        write f;
        n := n / f;
        <clone class=2>
            if n = 3 then
                n := 2;
            end
        </clone>
    end
    f := f + 1;
    <clone class=1>
        while (n / f) * f = n do
            write f;
            n := n / f;
        end
    </clone>
end
<linux> 

Example run 2 (with renamed clones):

<linux> cat cloneseg2.til
// Silly meaningless example with lots of renamed clones
var n;
write "Input n please";
read n;
var f;
var g;
f := 2;
g := 7;
while n != 1 do
    while (n / f) * f = n do
        write f;
        n := n / f;
    end
    if f = 3 then
        f := 2;
    end
    f := f + 1;
end
while (n / f) * f = n do
    write f;
    if n = 3 then
        n := 2;
    end
    n := n / f;
end
while n != 1 do
    while (n / f) * f = n do
        write f;
        n := n / f;
        if g = 3 then
            g := 2;
        end
    end
    f := f + 1;
    while (g / f) * f = g do
        write f;
        g := g / f;
    end
end

<linux> txl cloneseg2.til TILclonesrenamed.Txl
TXL v10.5 (22.9.07) (c)1988-2007 Queen's University at Kingston
Compiling TILclonesrenamed.Txl ... 
Parsing cloneseg2.til ...
Transforming ...

<clone_class class=1>
    while (x1 / x2) * x2 = x1 do
        write x2;
        x1 := x1 / x2;
    end
</clone_class>
<clone_class class=2>
    if x1 = 3 then
        x1 := 2;
    end
</clone_class>

var n;
write "Input n please";
read n;
var f;
var g;
f := 2;
g := 7;
while n != 1 do
    <clone class=1>
        while (n / f) * f = n do
            write f;
            n := n / f;
        end
    </clone>
    <clone class=2>
        if f = 3 then
            f := 2;
        end
    </clone>
    f := f + 1;
end
while (n / f) * f = n do
    write f;
    <clone class=2>
        if n = 3 then
            n := 2;
        end
    </clone>
    n := n / f;
end
while n != 1 do
    while (n / f) * f = n do
        write f;
        n := n / f;
        <clone class=2>
            if g = 3 then
                g := 2;
            end
        </clone>
    end
    f := f + 1;
    <clone class=1>
        while (g / f) * f = g do
            write f;
            g := g / f;
        end
    </clone>
end
<linux> 

-- JamesCordy - 16 Oct 2007

TXL solution to TIL Chairmarks #3.4, Constant folding, recognize and resolve opportunities to fold constant expressions.

Thie simple example demonstrates constant propagation and expression folding using TXL.

-- JamesCordy - 03 Jan 2008

File "TILconst.Txl"

% Constant propagation and folding for TIL
% Jim Cordy, January 2008

% Given a TIL program, recognize constant assignments to variables,
% and replace references to the variable with the constant (constant propagation),
% then recognize and compute constant expressions (constant folding).

% This program could be combined with other optimization rules such as
% code motion and redundant variable elimination to further optimize the result.


% Begin with the TIL base grammar, using precedence
#define PRIORITY
include "TIL.Grm"

% Preserve comments in this transformation
#pragma -comment

redefine statement
        ...
    |   [comment] [NL]
end redefine


% Main function - just apply stages of the transformation

function main
    replace [program]
        P [program]
    by
        P [propagateConstants]
          [foldConstantExpressions]
end function


% Constant propagation - find each constant assignment to a variable, 
% and if it is not assigned again then replace references with the constant

rule propagateConstants
    replace [repeat statement]
        Var [id] := Const [literal] ;
        Rest [repeat statement]
    deconstruct not * [statement] Rest
        Var := _ [expression] ;
    deconstruct * [primary] Rest
        Var
    by
        Var := Const;
        Rest [replaceExpn Var Const]
end rule

rule replaceExpn Var [id] Const [literal]
    replace [primary]
        Var
    by
        Const
end rule


% Constant folding - find and evaluate constant expressions

rule foldConstantExpressions
    replace [expression]
        E [expression]

    construct NewE [expression]
        E % Generic folding of pure constant expressions
          [resolveAddition] 
          [resolveSubtraction] 
          [resolveMultiplication] 
          [resolveDivision] 

          % Other special cases involving constants (examples only, could be others)
          [resolveAdd0]
          [resolveSubtract0]
          [resolveMultiply1Right]
          [resolveMultiply1Left]
          [resolveParentheses]

    % Continue until we don't find anything to fold
    deconstruct not NewE
        E
    by
        NewE
end rule

rule resolveAddition
    replace [expression]
        N1 [integernumber] + N2 [integernumber]
    by
        N1 [+ N2]
end rule

rule resolveSubtraction
    replace [expression]
        N1 [integernumber] - N2 [integernumber]
    by
        N1 [- N2]
end rule 

rule resolveMultiplication
    replace [term]
        N1 [integernumber] * N2 [integernumber]
    by
        N1 [* N2]
end rule 

rule resolveDivision
    replace [term]
        N1 [integernumber] / N2 [integernumber]
    by
        N1 [/ N2]
end rule

rule resolveParentheses
    replace [primary]
        ( N [integernumber] )
    by
        N
end rule

rule resolveAdd0
    replace [expression]
        P [primary] + 0
    by
        P
end rule

rule resolveSubtract0
    replace [expression]
        P [primary] - 0
    by
        P
end rule

rule resolveMultiply1Right
    replace [expression]
        P [primary] * 1
    by
        P
end rule

rule resolveMultiply1Left
    replace [expression]
        1 * P [primary]
    by
        P
end rule

Example run: "const.til" is a meaningless little program with lots of opportunities for constant propagation and folding.

<linux> cat const.til
// Silly meaningless example with opportunities to fold constants
var x; var y; var z; var a; var b; var c;
var d; var e; var j; var k; var m; var n; var r;
y := 1;
z := 2;
while 1 do
    x := y + z;
    a := 3;
    z := 5;
    j := 0;
    while j != 100 do
        r := 99;
        d := 7;
        k := a + z;
        b := j * z;
        d := (y + z) * d;
        e := (x + z) * r;
        j := j + 1;
    end 
    // This one is constant for sure!
    c := a + y;
    m := y * b;
    n := r * y;
end 

<linux> txl const.til TILconst.Txl
TXL v10.5 (11.12.07) (c)1988-2007 Queen's University at Kingston
Compiling TILconst.Txl ... 
Parsing const.til ...
Transforming ...

// Silly meaningless example with opportunities to fold constants
var x;
var y;
var z;
var a;
var b;
var c;
var d;
var e;
var j;
var k;
var m;
var n;
var r;
y := 1;
z := 2;
while 1 do
    x := 1 + z;
    a := 3;
    z := 5;
    j := 0;
    while j != 100 do
        r := 99;
        d := 7;
        k := 8;
        b := j * 5;
        d := 6 * d;
        e := (x + 5) * 99;
        j := j + 1;
    end
    // This one is constant for sure!
    c := 4;
    m := b;
    n := r;
end
<linux> 

-- JamesCordy - 03 Jan 2008

TXL solution to TIL Chairmarks #2.3, Declarations-to-global, move all declarations from any nesting level to the global scope.

-- JamesCordy - 02 Nov 2005

File "TILtoglobal.Txl"

% TXL transformation to move all declarations in a TIL program to the 
% beginning of the program, making their meaning explicit

% Jim Cordy, October 2005

% Based on the TIL base grammar
include "TIL.Grm"

% Preserve comments, we're probably going to maintain the result
include "TILCommentOverrides.Grm"

% Transformation rule to move all declarations to the beginning of the program -
% does it the easy obvious way, extracting them all, deleting them all, then
% putting the extracted ones first.  

function main
    % This is a function transformer, so it applies only once 
    replace [program]
        Program [statement*]

    % Use the type extractor to get all statements as a flat sequence,
    % then filter for declarations only
    construct Declarations [statement*]
            _ [^ Program] [removeNonDeclarations]

    % Make a copy of the program with all declarations removed
    construct ProgramSansDeclarations [statement*]
            Program [removeDeclarations]

    % The result is a program consisting of the sequence of all the
    % declarations concatenated with the original program without declarations
    by
            Declarations [. ProgramSansDeclarations]
end function

rule removeDeclarations
    % Rule to remove every declaration at every level from statements
    replace [statement*]
        Declaration [declaration]
        FollowingStatements [statement*]
    by
        FollowingStatements
end rule

rule removeNonDeclarations
    % Rule to remove all statements that are not declarations from statements
    replace [statement*]
        NonDeclaration [statement]
        FollowingStatements [statement*]

    % Check that the statement isn't a declaration 
    deconstruct not NonDeclaration
            _ [declaration]

    % If so, take it out
    by
        FollowingStatements
end rule

Example run: "vareg.til" is a meaningless little program with lots of data dependencies for demonstration purposes.

<linux> cat vareg.til
var d;
d := 17;
var r;
r := 5;
var y;
read y;
var z;
read z;
while y != 0 do
    var x;
    x := y + z;
    var a;
    a := 3;
    var j;
    j := 1;
    var b;
    while j != 100 do
        var k;
        k := a + z;
        b := j * z;
        d := (y + z) * d;
        var e;
        e := (x + z) * r;
        j := j + 1;
    end
    var c;
    c := a + y;
    var m;
    m := y * b;
    var n;
    n := r * y;
    write n;
    y := y - 1;
end
<linux> txl vareg.til TILtoglobal.Txl
TXL v10.4a (15.6.05) (c)1988-2005 Queen's University at Kingston
Compiling TILtoglobal.Txl ... 
Parsing vareg.til ...
Transforming ...
var d;
var r;
var y;
var z;
var x;
var a;
var j;
var b;
var k;
var e;
var c;
var m;
var n;
d := 17;
r := 5;
read y;
read z;
while y != 0 do
    x := y + z;
    a := 3;
    j := 1;
    while j != 100 do
        k := a + z;
        b := j * z;
        d := (y + z) * d;
        e := (x + z) * r;
        j := j + 1;
    end
    c := a + y;
    m := y * b;
    n := r * y;
    write n;
    y := y - 1;
end
<linux> 

TXL solution to TIL Chairmarks #2.4, Declarations-to-local, move all declarations to their most local location.

-- JamesCordy - 02 Nov 2005

File "TILtolocal.Txl"

% TXL transformation to move all declarations in a TIL program to their most local location

% Jim Cordy, October 2005

% Based on the TIL base grammar
include "TIL.Grm"

% Preserve comments, we're probably going to maintain the result
include "TILCommentOverrides.Grm"

% Transformation to move all declarations to their most local location -
% immediately before their first use, in the innermost block they can be.
% It is done as two rules - one that moves declarations across statements
% that do not depend on them, and one that moves declarations inside statements
% they are not used outside of.

rule main
    % Since this rule's pattern matches its result, it has no natural termination point
    replace [program]
        Program [program]

    % We therefore add an explicit fixed-point guard - after each application 
    % of the two base transformations, we check to see that something more was actually done
    construct NewProgram [program]
            Program [immediatizeDeclarations]
                [localizeDeclarations]
    deconstruct not NewProgram
            Program
    by
        NewProgram 
end rule

rule immediatizeDeclarations
    % Move all declarations past statements that don't depend on them
    % This rule uses a one-pass traversal ($) since the case of two declarations in a row
    % has no natural fixed point for this rule
    replace $ [statement*]
        'var V [id];
        Statement [statement]
        MoreStatements [statement*]

    % We can move the declaration past a statement if the statement does
    % not refer to the declared variable
    deconstruct not * [id] Statement
            V
    by
        Statement 
        'var V;
        MoreStatements
end rule

rule localizeDeclarations
    % Move any declarations outside a structured statement inside it if
    % the statements following it do not depend on the declared variable
    % Again, use a one pass ($) traversal
    replace $ [statement*]
        Declaration [declaration]
        CompoundStatement [statement]
        MoreStatements [statement*]

    % Check that it is some kind of compound statement (one with a statement list inside)
    deconstruct * [statement*] CompoundStatement
            _ [statement*]

    % Check that the following statements don't depend on the declaration
    deconstruct * [id] Declaration
            V [id]
    deconstruct not * [id] MoreStatements
            V

    % Alright, then maybe we can move it in.  This transformation uses the natural
    % example-base style of TXL, and thus does each kind of compound statement separately
    % Another solution might use agile parsing to abstract similar cases into one
    by
        CompoundStatement [injectDeclarationWhile Declaration] 
                          [injectDeclarationFor Declaration]
                          [injectDeclarationIfThen Declaration]
                          [injectDeclarationIfElse Declaration]
        MoreStatements 
end rule

function injectDeclarationWhile Declaration [declaration]
    % Note that there is no legal way that the while Expn can depend on the declaration,
    % since there are no assignments between the declaration and the Expn
    replace [statement]
            'while Expn [expression] 'do
            Statements [statement*]
        'end
    by
            'while Expn 'do
            Declaration
            Statements 
        'end
end function

function injectDeclarationFor Declaration [declaration]
    % Note that there is no legal way that the while Expn can depend on the declaration,
    % since there are no assignments between the declaration and the Expn
    replace [statement]
            'for Id [id] := Expn1 [expression] 'to Expn2 [expression] 'do
            Statements [statement*]
        'end
    by
            'for Id := Expn1 'to Expn2 'do
            Declaration
            Statements 
        'end
end function

function injectDeclarationIfThen Declaration [declaration]
    % Note that there is no legal way that the if Expn can depend on the declaration,
    % since there are no assignments between the declaration and the Expn
    replace [statement]
        'if Expn [expression] 'then
            ThenStatements [statement*]
         OptionalElse [opt else_statement]
        'end
    deconstruct Declaration
            'var V [id];
    deconstruct not * [id] OptionalElse
            V
    by
        'if Expn 'then
            Declaration
            ThenStatements 
         OptionalElse
        'end
end function

function injectDeclarationIfElse Declaration [declaration]
    % Note that there is no legal way that the if Expn can depend on the declaration,
    % since there are no assignments between the declaration and the Expn
    replace [statement]
        'if Expn [expression] 'then
            ThenStatements [statement*]
        'else
            ElseStatements [statement*]
        'end
    deconstruct Declaration
            'var V [id];
    deconstruct not * [id] ThenStatements
            V
    by
        'if Expn 'then
            ThenStatements 
        'else
            Declaration
            ElseStatements 
        'end
end function

Example run: "gvareg.til" is a meaningless little program with lots of data dependencies and all global declarations for demonstration purposes.

<linux> cat gvareg.til
// Meaningless example TIL program with lots of data dependencies
var d;
var r;
var y;
var z;
var x;
var a;
var j;
var b;
var k;
var e;
var c;
var m;
var n;
d := 17;
r := 5;
read y;
read z;
while y != 0 do
    x := y + z;
    a := 3;
    j := 1;
    while j != 100 do
        k := a + z;
        b := j * z;
        d := (y + z) * d;
        e := (x + z) * r;
        j := j + 1;
    end
    c := a + y;
    m := y * b;
    n := r * y;
    write n;
    y := y - 1;
end
<linux> txl gvareg.til TILtolocal.Txl
TXL v10.4a (15.6.05) (c)1988-2005 Queen's University at Kingston
Compiling TILtolocal.Txl ... 
Parsing gvareg.til ...
Transforming ...
// Meaningless example TIL program with lots of data dependencies
var d;
d := 17;
var r;
r := 5;
var y;
read y;
var z;
read z;
while y != 0 do
    var x;
    x := y + z;
    var a;
    a := 3;
    var j;
    j := 1;
    var b;
    while j != 100 do
        var k;
        k := a + z;
        b := j * z;
        d := (y + z) * d;
        var e;
        e := (x + z) * r;
        j := j + 1;
    end
    var c;
    c := a + y;
    var m;
    m := y * b;
    var n;
    n := r * y;
    write n;
    y := y - 1;
end
<linux> 

TXL solution to TIL Chairmarks #4.6: Clone detection. This example implements clone detection for exact clones of structured statements (if, while, for) in a TIL program and outputs the program with clones marked up using XML tags indicating the clone class of each instance.

-- JamesCordy - 15 Oct 2007

File "TILclonesexact.Txl"

% Clone detection on Tiny Imperative Language programs
% Jim Cordy, October 2007

% Given a TIL program, this program finds exact clones
% of stuctured statements (if, while and for statements)
% and outputs the program with exact clones marked up
% to indicate their clone class.  

% Usage:  txl program.til TILclonesexact.Txl > program.clones 

% Begin with the TIL base grammar
include "TIL.Grm"

% Overrides to conflate all structured statements into one nonterminal type.
% Putting [structured_statement] before existing statement forms makes
% it the preferred parse for the statements it matches.

redefine statement
        [structured_statement] 
    |   ...
end redefine

define structured_statement
        [if_statement]
    |   [for_statement]
    |   [while_statement]
end define

% Overrides to allow XML markup of TIL statements.

redefine statement
        ...
    |   [marked_statement]
end redefine

define marked_statement
        [xmltag]         [NL][IN] 
            [statement]  [EX] 
        [xmlend]         [NL]
end define

% [SPOFF] and [SPON] temporarily disable default spacing in tags

define xmltag
        < [SPOFF] [id] [SP] [id] = [number] > [SPON]
end define

define xmlend
        < [SPOFF] / [id] > [SPON]
end define


% Main program

function main
    replace [program]
        P [program]

    % First make a table of all repeated structured statements
    construct StructuredClones [repeat structured_statement]
        _ [findStructuredStatementClones P]

    % Now mark up all instances of each of them in the program
    % CloneNumber keeps track of the index of each one in the table as we step 
    % through it using 'each'
    export CloneNumber [number] 0
    by
        P [markCloneInstances each StructuredClones]
end function

% We make a table of the cloned structured statements by first making a table
% of all structured statements in the program, then looking for repeats

function findStructuredStatementClones P [program] 
    % Use the extract [^] function to make a table of all structured statements in the program
    construct StructuredStatements [repeat structured_statement]
            _ [^ P]
    % Now add each one that is repeated to the table of clones 
    replace [repeat structured_statement]
        % empty to begin with
    by
        _ [addIfClone StructuredStatements each StructuredStatements]
end function

function addIfClone StructuredStatements [repeat structured_statement] Stmt [structured_statement]
    % A structured statement is cloned if it appears twice in the table of all statements
    deconstruct * StructuredStatements
        Stmt
        Rest [repeat structured_statement]
    deconstruct * [structured_statement] Rest
        Stmt

    % If it does appear (at least) twice, add it to the table of clones 
    replace [repeat structured_statement]
        StructuredClones [repeat structured_statement]
    % Make sure it's not already in the table
    deconstruct not * [structured_statement] StructuredClones
        Stmt
    by
        StructuredClones [. Stmt]
end function

% Once we have the table of all clones, we mark up each instance of each of them
% in the program with its clone class, that is, the index of it in the clone table

rule markCloneInstances StructuredClone [structured_statement]
    % Keep track of the index of this clone in the table
    import CloneNumber [number]
    export CloneNumber 
        CloneNumber [+ 1]

    % Mark up all instances of it in the program
    % 'skipping' avoids marking any instance twice
    skipping [marked_statement]
    replace [statement]
        StructuredClone
    by
        <clone class=CloneNumber> StructuredClone </clone>
end rule

Example run:

<linux> cat cloneseg1.til
// Silly meaningless example with lots of exact clones
var n;
write "Input n please";
read n;
var f;
f := 2;
while n != 1 do
    while (n / f) * f = n do
        write f;
        n := n / f;
    end
    if n = 3 then
        n := 2;
    end
    f := f + 1;
end
while (n / f) * f = n do
    write f;
    if n = 3 then
        n := 2;
    end
    n := n / f;
end
while n != 1 do
    while (n / f) * f = n do
        write f;
        n := n / f;
        if n = 3 then
            n := 2;
        end
    end
    f := f + 1;
    while (n / f) * f = n do
        write f;
        n := n / f;
    end
end

<linux> txl cloneseg1.til TILclonesexact.Txl
TXL v10.5 (22.9.07) (c)1988-2007 Queen's University at Kingston
Compiling TILclonesexact.Txl ... 
Parsing cloneseg1.til ...
Transforming ...
var n;
write "Input n please";
read n;
var f;
f := 2;
while n != 1 do
    <clone class=1>
        while (n / f) * f = n do
            write f;
            n := n / f;
        end
    </clone>
    <clone class=2>
        if n = 3 then
            n := 2;
        end
    </clone>
    f := f + 1;
end
while (n / f) * f = n do
    write f;
    <clone class=2>
        if n = 3 then
            n := 2;
        end
    </clone>
    n := n / f;
end
while n != 1 do
    while (n / f) * f = n do
        write f;
        n := n / f;
        <clone class=2>
            if n = 3 then
                n := 2;
            end
        </clone>
    end
    f := f + 1;
    <clone class=1>
        while (n / f) * f = n do
            write f;
            n := n / f;
        end
    </clone>
end
<linux> 

-- JamesCordy - 15 Oct 2007

TXL solution to TIL Chairmarks #2.1, declaring "for" statement to nondeclaring "for" statement.

-- JamesCordy - 10 Oct 2005

File "TILfordeclare.Txl"

% TXL transformation to adapt existing "declaring for" semantics TIL programs
% to a proposed new semantics in which "for" control variables must be declared
% Jim Cordy, October 2005

% Note: In this program all keywords of TIL are quoted in patterns and replacements -
% this is not strictly necessary, but is conventional style in modern TXL programs.

% Based on the TIL base grammar
include "TIL.Grm"

% Preserve comments, we're probably going to maintain the result
include "TILCommentOverrides.Grm"

% Transformation rule to correct all for loops.

% Default rewrite rule semantics in TXL are compositional fixed point,
% which for most transformations is the desired semantics.  However,
% this transformation has no syntactic compositional fixed point.
% So the alternatives are either a semantically-guarded transformation,
% a grammar override, or an explicit once-over traversal.
% This solution uses the last of these, not because it is the best solution
% but because this example gives us an opportunity to demonstrate that possibility.

function main
    % This is a function transformer, so it applies only once unless explicitly
    % reapplied.  The "replace *" allows it to search deeply for its pattern.
    % The replacement reapplies it twice to implement an explicit traversal.

    replace * [statement*]
        'for Id [id] := Expn1 [expression] 'to Expn2 [expression] 'do
            Statements [statement*]
        'end
        MoreStatements [statement*]
    by
        'var Id;
        'for Id := Expn1 'to Expn2 'do
            Statements [main]
        'end
        MoreStatements [main]
end function

Example run:

<linux> cat multiples.til 
// Test of declaring for loop in TIL
// Output first 10 multiples of numbers 1 through 9
for i := 1 to 9 do
for j := 1 to 10 do
    write i*j;
end end
<linux> txl multiples.til TILfordeclare.Txl 
TXL v10.4a (15.6.05) (c)1988-2005 Queen's University at Kingston
Compiling TILfordeclare.Txl ... 
Parsing multiples.til ...
Transforming ...
// Test of declaring for loop in TIL
// Output first 10 multiples of numbers 1 through 9
var i;
for i := 1 to 9 do
    var j;
    for j := 1 to 10 do
        write i * j;
    end
end
<linux> 

TXL solution to TIL Chairmarks #2.2, transform all "for" statements to their equivalent "while" statement form.

-- JamesCordy - 10 Oct 2005

File "TILfortowhile.Txl"

% Convert Tiny Imperative Language "for" statements to "while" form
% Jim Cordy, August 2005

% This program converts all "for" statements in a TIL program to
% their equivalent "while" form

% Some details assumed:
%
% - It is not clear whether TIL is scoped or not.  We assume not
%   since there is no explicit scoping statement in the language.
%
% - The "for" statement of TIL is a "declaring for".
%   We assume this means it automatically declares its control variable.
%
% These assumptions can be trivially changed here if TIL changes.

% Based on the TIL grammar
include "TIL.grm"

% Preserve comments in output
include "TILCommentOverrides.Grm"

% Rule to convert every "for" statement
rule main
    % Capture each "for" statement, in its statement sequence context
    % so that we can replace it with multiple statements
    replace [statement*]
        'for Id [id] := Expn1 [expression] 'to Expn2 [expression] 'do
            Statements [statement*]
        'end
        MoreStatements [statement*]

    % Need a unique new identifier for the upper bound
    construct UpperId [id]
        Id [_ 'Upper] [!]

    % Construct the iterator
    construct IterateStatement [statement]
        Id := Id + 1;

    % Replace the whole thing
    by
        'var Id;
        Id := Expn1;
        'var UpperId;
        UpperId := (Expn2) + 1;
        'while Id - UpperId 'do
            Statements [. IterateStatement]
        'end
        MoreStatements
end rule

Example run:

<linux> cat multiples.til
// Test of declaring for loop in TIL
// Output first 10 multiples of numbers 1 through 9
for i := 1 to 9 do
for j := 1 to 10 do
    write i*j;
end end
<linux> txl multiples.til TILfortowhile.Txl
TXL v10.4a (15.6.05) (c)1988-2005 Queen's University at Kingston
Compiling TILfortowhile.Txl ... 
Parsing multiples.til ...
Transforming ...
// Test of declaring for loop in TIL
// Output first 10 multiples of numbers 1 through 9
var i;
i := 1;
var i_Upper1;
i_Upper1 := (9) + 1;
while i - i_Upper1 do
    var j;
    j := 1;
    var j_Upper1;
    j_Upper1 := (10) + 1;
    while j - j_Upper1 do
        write i * j;
        j := j + 1;
    end
    i := i + 1;
end
<linux> 

TXL solution to TIL Chairmarks #2.5, Goto elimination, recognize and transform while-equivalent goto structures.

-- JamesCordy - 31 Dec 2007

File "TILgotoelim.Txl"

% Goto elimination in TIL programs
% Jim Cordy, January 2008

% Given a TIL program in an extended dialect that includes labelled statements 
% and goto statements, recognize and resolve while-equivalent goto structures.

% Begin with the TIL base grammar
include "TIL.Grm"

% Preserve comments in this transformation
#pragma -comment

% Add labels and goto statements to TIL 
redefine statement
        ...
    |        [labelled_statement]
    |        [goto_statement]
    |        [null_statement]
    |        [comment_statement]
end redefine

define labelled_statement
        [label] ': [statement] 
end define

define goto_statement
        'goto [label] ';  [NL]
end define

% Allow for trailing labels
define null_statement
        [NL]
end define

define comment_statement
        [comment]  [NL]
end define

define label 
        [id]
end define


% Main program - just applies the rules for cases we know how to transform 

function main
    replace [program]
        P [program]
    by
        P [transformForwardWhile]
          [transformBackwardWhile]
end function


% Case 1 - structures of the form
%        loop:
%            if Cond then goto endloop; end
%            LoopStatements
%            goto loop;
%        endloop:
%            TrailingStatements

rule transformForwardWhile
    replace [repeat statement]
        L0 [label] ': 
            'if X [expression] Op [op] Y [expression] 'then
                'goto L1 [label] ';
            'end
        Rest [repeat statement]
    skipping [statement]
    deconstruct * Rest
        'goto L0 ';
        L1 ':
            Follow [statement]
        FinalRest [repeat statement]
    construct NonRest [repeat statement]
        Rest [truncateGoto L0 L1]
    by
        'while X Op [invertOp] Y 'do
            NonRest
        'end
        Follow
        FinalRest
end rule

function truncateGoto L0 [label] L1 [label]
    replace * [repeat statement]
        'goto L0 ';
        L1 ':
            Follow [statement]
        FinalRest [repeat statement]
    by
        % nothing
end function

% Since TIL doesn't have a not operator, we need to invert comparisons
function invertOp
    construct Ops [repeat op]
        '= '!=
    construct InvertOps [repeat op]
        '!= '=
    replace [op]
        Op [op]
    by
        Op [replaceOriginalOp Op each Ops InvertOps]
end function

function replaceOriginalOp OriginalOp [op] PatternOp [op] ReplacementOp [op]
    replace [op]
        OriginalOp 
    by
        OriginalOp [$ PatternOp ReplacementOp]
end function


% Case 2 - structures of the form
%        loop:
%            LoopStatements
%            if Cond then goto loop; end
%        TrailingStatements

rule transformBackwardWhile
    replace [repeat statement]
        L0 [label] ': 
            First [statement]
        Rest [repeat statement]
    skipping [statement]
    deconstruct * Rest
        'if C [expression] 'then
            'goto L0 ';
        'end
        FinalRest [repeat statement]
    construct NonRest [repeat statement]
        Rest [truncateIfGoto L0]
    construct WhileStatement [repeat statement]
        'while C 'do
            First
            NonRest
        'end
    by
        First
        NonRest [. WhileStatement]
                [. FinalRest]
end rule

function truncateIfGoto L0 [label]
    skipping [statement]
    replace * [repeat statement]
        'if C [expression] 'then
            'goto L0 ';
        'end
        FinalRest [repeat statement]
    by
        % nothing
end function

Example run: "gotofactors.til" is a goto-based version of the factors.til example program.

<linux> cat gotofactors.til
// Factor an input number - goto version
var n;
var f;
write "Input n please";
read n;
write "The factors of n are";
f := 2;
// Outer loop over potential factors
factors:
    if  n = 1 then
        goto endfactors;
    end
// Inner loop over multiple instances of same factor
multiples: 
    if (n / f) * f != n then
        goto endmultiples;
    end
    write f;
    n := n / f;
    goto multiples;
endmultiples:
    f := f + 1;
    goto factors;
endfactors:

<linux> txl gotofactors.til TILgotoelim.Txl 
TXL v10.5 (11.12.07) (c)1988-2007 Queen's University at Kingston
Compiling TILgotoelim.Txl ... 
Parsing gotofactors.til ...
Transforming ...

// Factor an input number - goto version
var n;
var f;
write "Input n please";
read n;
write "The factors of n are";
f := 2;
// Outer loop over potential factors
while n != 1 do
    // Inner loop over multiple instances of same factor
    while (n / f) * f = n do
        write f;
        n := n / f;
    end
    f := f + 1;
end

<linux>

Grammar Overrides refer to nonterminal modifications or extensions to a fixed base grammar for the purpose of extending the language or customizing the parse to the task (Agile Parsing^?). Grammar Overrides are most obvious and convenient in TXL, which has an explicit feature for implementing them, but are a general concept used in many source transformation systems. They can be implemented any number of ways including using Grammar Adaptation^?, Grammar Transformation^? or by hand using cloning of the original base grammmar.

-- JamesCordy - 10 Oct 2005

A more sophisticated TXL solution to TIL Chairmarks #3.1, Move all invariant assigned computations outside of while loops.

This is a more sophisticated version of Lift Invariant Assignments Using TXL, which uses renaming of masking assignments in a loop to expose more opportunities to move assigned computations out of the loop. See the original for the basics of code motion in TXL, and this one for the renaming aspect.

-- JamesCordy - 04 Nov 2005

File "TILcodemotion2.Txl"

% Lift independent assigned computations outside of TIL while loops
% J.R. Cordy, November 2005

% This more sophisitcated TXL program will optimize a TIL program by moving all 
% assigned computations not dependent on computation inside while loops to the outside.
% The process works in two steps: 
%   (1) Renaming of masking assignments (subsequent assignments to a variable), 
%       which exposes hidden opportunities for code motion, and 
%   (2) Lifting of independent assignments, exactly as in the simpler assignment
%       only case in TILcodemotion.Txl
% Finally, declarations are synthesized and inserted for any new variables introduced 
% by the renaming.

% Based on the TIL grammar
include "TIL.Grm"

% Two main parts - the actual renaming and lifting, then the introduction of missing 
% declarations for any introduced renamed variables
function main
    replace [program]
        P [program]
    by
        P [renameAndLift]
          [declareNewVariables]
end function


% Main rule: Rename masking assignments and lift them outside loops until no more can be 
% renamed and no more can belifted
rule renameAndLift
    replace [program]
        P [program]

    % We continue as long as a match for either transform can be found - the form [?rule] 
    %   in TXL means test if a pattern match for the rule can be found
    % In TXL, the composition of two conditionals is "or", so this guard tests whether
    %   either rule can find a match
    where
        P [?renameMaskingAssignments]
          [?liftLoopAssignments]

    % If so, apply the rules and continue until the condition above fails 
    by
        P [renameMaskingAssignments]
          [liftLoopAssignments]
end rule


% Ruleset 1: Rename any masking assignments (i.e., re-assignments to the same variable)
% This exposes hidden opportunities to move assigned computations out of the loop
rule renameMaskingAssignments
    % Find every while loop
    replace [statement*]
        while Expn [expression] do
            Body [statement*]
        'end
        Rest [statement*]

    % Keep renaming until there are no more to rename
    where
        Body [?renameAssignment Body]
    by
        while Expn do
            Body [renameAssignment Body]
        'end 
        Rest
end rule

% Rename repeated assignments
rule renameAssignment Body [statement*]
    % Find an assignment
    replace [statement*]
        X [id] := E [expression];
        Rest [statement*]

    % Construct the context it appears in
    construct PreContext [statement*]
        Body [deleteAssignmentAndRest X]

    % Rename any subsequent assignment to X, if possible
    where
        Rest [?renameAssignmentsTo X PreContext]
    by
        X := E;
        Rest [renameAssignmentsTo X PreContext]
end rule

% Rename any subsequent assignment to X, if possible
rule renameAssignmentsTo X [id] PreContext [statement*]
    % Find a subsequent assignment to X
    replace [statement*]
        X := E [expression];
        Rest [statement*]

    % It only makes sense to rename it if its effect doesn't wrap around ...
    where not 
        PreContext [refers X]

    % ... and it is not an iteration 
    where not
        E [refers X]

    % ... and it is not assigned again
    where not
        Rest [assigns X]

    % If all that is ok, then rename it
    construct NewX [id]
        X [!]
    by  
        NewX := E;
        Rest [$ X NewX]      % [$ X NewX] means substitute NewX for X everywhere in Rest
end rule


% Ruleset 2: Lift all independent assignments out of loops
% This is exactly the same ruleset as in TILcodemotion.Txl - we could use a TXL "include"
% statement to reuse the original
rule liftLoopAssignments
    % Find every loop
    replace [statement*]
        while Expn [expression] do
            Body [statement*]
        'end 
        Rest [statement*]

    % Construct a list of all the top-level assignments in it
    construct AllAssignments [statement*]
        Body [deleteNonAssignments]

    % Construct a copy of the loop to work on
    construct LiftedLoop [statement*]
        while Expn do
            Body 
        'end 

    % Only proceed if there are assignments left that can be lifted out
    % The [?loopLift] form tests if the pattern of the [loopLift] rule can be matched -
    % "each AllAssignments" tests this for any of the top-level internal assignments
    where
        LiftedLoop [?loopLift Body each AllAssignments]

    % If the above guard succeeds, some can be moved out, so go ahead and move them,
    % replacing the original loop with the result
    by
        LiftedLoop [loopLift Body each AllAssignments]
        [. Rest]
end rule

% Attempt to lift a given assignment outside the loop
function loopLift Body [statement*] Assignment [statement]
    deconstruct Assignment
        X [id] := E [expression];

    % Extract a list of all the identifiers used in the expression
    construct IdsInExpression [id*]
        _ [^ E]

    % Replace the loop and its contents
    replace [statement*]
        Loop [statement*]

    % We can only lift the assignment out if all the identifiers in its
    % expression are not assigned in the loop ...
    where not
        Loop [assigns each IdsInExpression]

    % ... and X itself is assigned only once
    deconstruct * Body
        X := _ [expression];
        Rest [statement*]
    where not
        Rest [assigns X]

    % ... and the the effect of it does not wrap around the loop
    construct PreContext [statement*]
        Body [deleteAssignmentAndRest X]
    where not
        PreContext [refers X]

    % Now lift out the assignment
    by
        Assignment
        Loop [deleteAssignment Assignment]
end function


% Utility rules used above

% Delete a given assignment statement from a scope
function deleteAssignment Assignment [statement]
    replace * [statement*]
        Assignment
        Rest [statement*]
    by
        Rest
end function

% Delete all non-assignment statements in a scope -
% given a scope, yields the assignments only
rule deleteNonAssignments
    replace [statement*]
        S [statement]
        Rest [statement*]
    deconstruct not S
        _ [assignment_statement]
    by
        Rest
end rule

% Delete everything in a scope from the assignment to X on -
% given a scope and X, yields the context of the first assignment to X
function deleteAssignmentAndRest X [id]
    replace * [statement*]
        X := E [expression];
        Rest [statement*]
    by
        % nada
end function

% Condition - given a scope, does the scope assign to the identifier?
function assigns Id [id]
    match * [assignment_statement]
        Id := Expn [expression];
end function

% Condition - given a scope, does the scope refer to the identifier?
function refers Id [id]
    match * [id]
        Id
end function


% Ruleset 3: Declare any renaming variables we introduced
rule declareNewVariables
    replace [program]
        P [program]
    % Continue until we can't find any more
    where
        P [?declareNewVariable P]
    by
        P [declareNewVariable P]
end rule

function declareNewVariable P [program]
    replace * [statement*]
        X [id] := E [expression];
        MoreStatements [statement*]
    deconstruct not * [declaration] P
        'var X;
    by
        'var X;
        X := E;
        MoreStatements 
end function

Example run: "lift2.til" is a meaningless little program intended to demonstrate the difference between the simple assignment code motion solution of Lift Invariant Assignments using TXL and the more sophisticated one above. We first run the simple solution, and no opportunities for code motion are found. Then we run the solution above, which renames masking assignments to expose two computations that can be moved out of the loop.

<linux> cat lift2.til
var a; var b; var c; 
var x; var y; var z;
while 1 do
    x := a + b;
    y := x;
    a := y + 3;
    x := b + c;
    y := x - 2;
    z := x + a * y;
end
<linux> txl lift2.til TILcodemotion.Txl
TXL v10.4a (15.6.05) (c)1988-2005 Queen's University at Kingston
Compiling TILcodemotion.Txl ... 
Parsing lift2.til ...
Transforming ...
var a;
var b;
var c;
var x;
var y;
var z;
while 1 do
    x := a + b;
    y := x;
    a := y + 3;
    x := b + c;
    y := x - 2;
    z := x + a * y;
end
<linux> txl lift2.til TILcodemotion2.Txl
TXL v10.4a (15.6.05) (c)1988-2005 Queen's University at Kingston
Compiling TILcodemotion2.Txl ... 
Parsing lift2.til ...
Transforming ...
var a;
var b;
var c;
var x;
var y;
var z;
var x4;
x4 := b + c;
var y2;
y2 := x4 - 2;
while 1 do
    x := a + b;
    y := x;
    a := y + 3;
    z := x4 + a * y2;
end
<linux> 

TXL solution to TIL Chairmarks #3.1, Move all invariant assignments outside of while loops.

This is a simple demonstration of the basics of data flow checking and code motion using TXL. For TIL this is not very challenging. In real languages and applications, more sophisticated data flow and alias analysis across procedures is needed. In TXL this more sophisticated analysis is done using source code markup to localize dependency information before actual code movement.

-- JamesCordy - 03 Nov 2005

File "TILcodemotion.Txl"

% Lift independent assignments outside of TIL while loops
% J.R. Cordy, November 2005

% This TXL program will optimize a TIL program by moving all assignments 
% not dependent on computation inside while loops to the outside.  
% For loops can be done similarly, but are not handled by this program.

% Based on the TIL grammar
include "TIL.Grm"

% Lift all independent assignments out of loops
rule main
    % Find every loop
    replace [statement*]
        while Expn [expression] do
            Body [statement*]
        'end 
        Rest [statement*]

    % Construct a list of all the top-level assignments in it
    construct AllAssignments [statement*]
        Body [deleteNonAssignments]

    % Construct a copy of the loop to work on
    construct LiftedLoop [statement*]
        while Expn do
            Body 
        'end 

    % Only proceed if there are assignments left that can be lifted out
    % The [?loopLift] form tests if the pattern of the [loopLift] rule can be matched -
    % "each AllAssignments" tests this for any of the top-level internal assignments
    where
        LiftedLoop [?loopLift Body each AllAssignments]

    % If the above guard succeeds, some can be moved out, so go ahead and move them,
    % replacing the original loop with the result
    by
        LiftedLoop [loopLift Body each AllAssignments]
        [. Rest]
end rule

% Attempt to lift a given assignment outside the loop
function loopLift Body [statement*] Assignment [statement]
    deconstruct Assignment
        X [id] := E [expression];

    % Extract a list of all the identifiers used in the expression
    construct IdsInExpression [id*]
        _ [^ E]

    % Replace the loop and its contents
    replace [statement*]
        Loop [statement*]

    % We can only lift the assignment out if all the identifiers in its
    % expression are not assigned in the loop ...
    where not
        Loop [assigns each IdsInExpression]

    % ... and X itself is assigned only once
    deconstruct * Body
        X := _ [expression];
        Rest [statement*]
    where not
        Rest [assigns X]

    % ... and the the effect of it does not wrap around the loop
    construct PreContext [statement*]
        Body [deleteAssignmentAndRest X]
    where not 
        PreContext [refers X]

    % Now lift out the assignment
    by
        Assignment
        Loop [deleteAssignment Assignment]
end function


% Utility rules used above

% Delete a given assignment statement from a scope
function deleteAssignment Assignment [statement]
    replace * [statement*]
        Assignment
        Rest [statement*]
    by
        Rest
end function

% Delete all non-assignment statements in a scope - 
% given a scope, yields the assignments only
rule deleteNonAssignments
    replace [statement*]
        S [statement]
        Rest [statement*]
    deconstruct not S
        _ [assignment_statement]
    by
        Rest
end rule

% Delete everything in a scope from the first assignment to X on -
% given a scope and X, yields the context of the first assignment to X
function deleteAssignmentAndRest X [id]
    replace * [statement*]
        X := E [expression];
        Rest [statement*]
    by
        % nada
end function

% Condition - given a scope, does the scope assign to the identifier?
function assigns Id [id]
    match * [assignment_statement]
        Id := Expn [expression];
end function

% Condition - given a scope, does the scope refer to the identifier?
function refers Id [id]
    match * [id]
        Id
end function

Example run: "lift.til" is a meaningless little program with lots of data dependencies, lots of opportunities for code motion, and all global declarations for demonstration purposes only.

<linux> cat lift.til
var x; var y; var z; var a; var b; var c;
var d; var e; var j; var k; var m; var n; var r;
y := 1;
z := 2;
while 1 do
    x := y + z;
    a := 3;
    z := 5;
    j := 0;
    while j != 100 do
        r := 99;
        d := 7;
        k := a + z;
        b := j * z;
        d := (y + z) * d;
        e := (x + z) * r;
        j := j + 1;
    end 
    c := a + y;
    m := y * b;
    n := r * y;
end 

<linux> txl lift.til TILcodemotion.Txl
TXL v10.4a (15.6.05) (c)1988-2005 Queen's University at Kingston
Compiling TILcodemotion.Txl ... 
Parsing lift.til ...
Transforming ...
var x;
var y;
var z;
var a;
var b;
var c;
var d;
var e;
var j;
var k;
var m;
var n;
var r;
y := 1;
z := 2;
a := 3;
c := a + y;
r := 99;
n := r * y;
while 1 do
    x := y + z;
    z := 5;
    j := 0;
    k := a + z;
    e := (x + z) * r;
    while j != 100 do
        d := 7;
        b := j * z;
        d := (y + z) * d;
        j := j + 1;
    end
    m := y * b;
end
<linux> 

The sts mailinglist has been created following a discussion at the end of the STS workshop on Sunday October 24, 2004.

General information about the mailing list is at:

• http://urchin.earth.li/mailman/listinfo/sts

TXL solution to TIL Chairmarks #4.1: Removing redundant declarations.

-- JamesCordy - 04 Jul 2006

File "TILredundant.Txl"

% TXL transformation to remove unused declarations in a TIL program
% Jim Cordy, July 2006

% Based on the TIL base grammar
include "TIL.Grm"

% Preserve comments, we're probably going to maintain the result
include "TILCommentOverrides.Grm"

% Transformation rule to remove all redundant variable declarations from a program.
% If a declared variable is not mentioned by the following statements, it is not used.

rule main
    % Find each variable declaration
    replace [statement*]
        'var Id [id] ';
        FollowingStatements [statement*]

    % Check to see if the declared identifier does not appear in the following statements
    deconstruct not * [id] FollowingStatements
        Id

    % If not, the declaration is redundant so we remove it
    by
        FollowingStatements
end rule

Example run:

<linux> cat redundantvareg.til
// Meaningless example TIL program with some redundant declarations
// (the ones with names like rr, rx, ry, rm)
var d;
var y;
d := 17;
read y;
var rr;
while y != 0 do
    var rx;
    var a;
    a := 3;
    var j;
    j := 1;
    while j != 100 do
        a := a * 2;
        var ry;
        j := j + 1;
    end
    var c;
    c := a + j;
    var n;
    n := c * y;
    write n;
    y := y - 1;
    var rm;
end
<linux> txl redundantvareg.til TILredundant.Txl 
TXL v10.4c (15.3.06) (c)1988-2006 Queen's University at Kingston
Compiling TILredundant.Txl ... 
Parsing redundantvareg.til ...
Transforming ...
// Meaningless example TIL program with some redundant declarations 
// (the ones with names like rr, rx, ry, rm)
var d;
var y;
d := 17;
read y;
while y != 0 do
    var a;
    a := 3;
    var j;
    j := 1;
    while j != 100 do
        a := a * 2;
        j := j + 1;
    end
    var c;
    c := a + j;
    var n;
    n := c * y;
    write n;
    y := y - 1;
end
<linux> 

Robust Parsing refers to one of a number of methods for modifying a grammar or parser in such a way as to allow for parsing to continue in the presence of parts of the input unexplained by the language grammar (i.e., syntax errors in the input). Typically this involves producing a parse tree in which unparseable sections of input are isolated into uninterpreted nodes containing the original input text.

-- JamesCordy - 10 Oct 2005

Software Transformation Systems Workshop 2004

STS04 was arranged Sunday, October 24th 2004 as part of Generative Programming and Component Engineering 2004 (GPCE'04), Vancouver, Canada, October 2004. The workshop organisers were

• Magne Haveraaen, University of Bergen, Norway
• Jim Cordy, Queen's University, Canada
• Jan Heering, CWI, Amsterdam, Netherlands
• Ganesh Sittampalam, Oxford University, UK

The workshop attracted roughly 30 participants. The day was divided into 4 presentation sessions of 1.5 hours and a 1 hour discussion session at the end, giving room for 22 position papers, which were selected from roughly 30 submissions. Each presentation session had 5-6 presentations of 10 minutes each, and 1/2 hour for discussions. The discussions were based on research questions, one posed by each presenter.

The position papers are collected into a pdf file:

Haveraaen, Cordy, Heering, Sittampalam: Position papers from Software Transformation Systems Workshop 2004.

Most of the slides from the individual presentations are available:

• Ira D. Baxter: Program Generation and Modification using Multiple Domains
• Paulo Henrique Monteiro Borba: A Transformation System for Java
• Marat Boshernitsan: Code Generation via Interactive Source-to-Source Transformations
• Thomas Cleenewerck: Invasive Composition by Transformation Systems
• Jim Cordy: Metaprogram Implementation by Second Order Source Transformation
• Anthony Cox: Lexical Source-Code Transformation
• Magne Haveraaen: Source Transformation Systems supporting Software Engineering
• Gorel Hedin: Towards comparing Transformation Systems and Formalisms
• Jan Heering: Generic Software Transformations
• Karl Trygve Kalleberg: Tracing Abstractions through Generation
• Marcelo Sant'Anna: Transformation Circuits: Exploring new Paradigms for Software Transformation Systems
• Shane Sendall: Understanding Model Transformation by Classification and Formalization
• Ganesh Sittampalam: abc: Extending Java to AspectJ^?
• Tony Sloane: Formal Integration of Generation Tools
• Douglas R. Smith: Requirements and Automated Refinement
• Eric Van Wyk: Semantic Analysis in Software Transformation
• L. Robert Varney: Generative Programming, Interface-Oriented Programming, and Source Transformation Systems
• J.J. Vinju: Combining Formalisms for Software Transformation - ASF+SDF Meta-Environment
• Eelco Visser: Reusable and Adaptive Strategies for Generative Programming
• Hironori Washizaki: Transforming Object-Oriented Programs into Structurally Reusable Components
• David Wile: Transformation Systems for DSLs, Architecture Styles, and Graphical Languages

The day was timetabled as follows:

• 08:30-10:00 session 1: Sittampalam, Borba, Kalleberg, Vinju, Visser
• 10:00-10:30 break
• 10:30-12:00 session 2: Cordy, Boshernitsan, Parr, Sloane, Smith, Varney
• 12:00-13:00 lunch
• 13:00-14:30 session 3: Haveraaen, Baxter, Cleenewerck, Washizaki, Wyk
• 14:30-14:50 break
• 14:50-16:20 session 4: Heering, Hedin, Sant'Anna, Sendall, Wile, Cox
• 16:20-16:30 break
• 16:30-17:30 final discussion

---

STS'06: Software Transformation Systems Workshop

part of the

Fifth international conference on
Generative Programming and Component Engineering (GPCE'06)

October 22-26, 2006, Portland, Oregon

colocated with OOPSLA'06

---

Workshop Organisers

• Magne Haveraaen, University of Bergen, Norway
• Jim Cordy, Queen's University, Canada
• Jan Heering, CWI, Amsterdam, Netherlands
• Eelco Visser, Utrecht University, Netherlands

Important Dates

Workshop schedule:

• 2 page position paper submission deadline: July 15, 2006
• Notification of acceptance: August 31, 2006
• GPCE/OOPSLA registration deadline: September 15 (early)/ October 5, 2006
• Workshop: Sunday October 22, 2006

Motivation

Generative software techniques typically transform components or codefragments, instantiate patterns etc. in some way or another to generate new code fragments, components or programs. Often this needs software support beyond that of existing compilers, i.e., some kind of system which takes software as inputs and produces software as output.

Software transformation systems are tools which are built for such transformations. They range from specific tools for one purpose, via simple pattern matching systems, to general transformation systems which are easily programmed to do any reasonable transformation. Thus the more general tools may be treated as meta-tools for generative programming.

Following on the success of STS'04, this workshop is once again designed to bring together people working on software transformation systems and those with an interest in software transformation systems as a generative tool, with the aim of investigating the use of software transformation tools as tools to support generative programming. We want to look at various generative techniques and suggest how these may be supported by various general purpose transformation tools. This may lead to a more general understanding of common principles for supporting generative methods.

This year's workshop will particularly focus on architecture, reuse, implementation (data representations and algorithms), application models and benchmarks, although contributions on a wide range of topics in the application of software transformation systems in generative techniques are sought.

Workshop format

The workshop will have a small number of participants, around 20, selected on the basis of short position papers submitted to the organisers. The aim is to let people with different perspectives meet in order to allow fruitful interaction.

Program

• 0830-1000 Specific transformation system (toolkits)
  Chair: Eelco Visser
  • Drew Hoskins: Background on Phoenix
  • Pierre-Etienne Moreau, Antoine Reilles: Strategic programming in Java
  • Andreas I. Schmied: The AspectIX Transformation Process Language
  • Victor L. Winter, Christopher Scalzo, Arpit Jain, Brent Kucera, Azamatbek Mametjanov: Comprehension of Generative Techniques
• Coffee break

• 1030-1200 Impact of transformation systems
  Chair: Jan Heering
  The following three papers discuss different angles of the problem of impact of transformation research in industry and the scattering of research efforts. The papers will give rise to plenty discussion, which hopefully will continue into lunch.
  • Martin Bravenboer: Impact of Software Transformation Systems on Language Workbenches and Domain-Specific Language Tools
  • Karl Trygve Kalleberg: Improving the Reuse of Language Infrastructures
  • Tony Sloane, Shirley Goldrei: Towards a coordinated approach to software transformation
  • Jurgen J. Vinju: UPTR: a simple parse tree representation format
• Lunch break

• 1330-1500 Requirements on program transformation techniques
  Chair: Jim Cordy
  Challenges and possible solutions to improve program transformation systems.
  • Eelco Visser: Transformations for Abstractions
  • Daniel J. Quinlan, Richard Vuduc: Requirements for Domain-Specific Source-to-Source Translation
  • Ewen Denney, Bernd Fischer, Johann Schumann: Using Software Transformation Systems as Program Generator Backends
  • Chung-Horng Lung: Moving towards Architecture Driven Software Transformation
• Coffee break

• 1530-1700 Applications of program transformation
  Chair: Magne Haveraaen
  • Ralf Lammel: Evolution-enabled application-programming interfaces
  • Ashley W. Brown, Wayne Luk, Paul H.J. Kelly: Generating Hardware Designs by Source Code Transformation
  • Elizabeth Dancy, Jim Cordy: Generating Software Tuning Panels for Autonomic Control
  • I. Karlin, Jean Utke: Source Transformations for Automatic Differentiation controlled by Performance Metrics

Each speaker is given 15 minutes for presentation and quick questions. The remainder of the session is for discussing the topics raised by the speakers.

Submission of intent to participate

If you find this workshop interesting you should send an e-mail to sts06@ii.uib.no with your intent to participate and your area of expertise/interest. Space may be limited at the workshop, and registered participants will be given priority.

Registration

Workshop participants should register for the GPCE'06 conference. Those who only wish to participate in the workshop should register for any one day of the conference. The badge will let you attend the workshop as well as the chosen day of the conference.

2004-12-23

Proceedings of the STS04 workshop are now available.

2004-11-01

Creation of the Sts web as website for the Software Transformation Systems community.

WebNotify is a subscription service to be automatically notified by email when topics change in the TWiki.Sts web. This is a convenient service, so you do not have to come back and check all the time if something has changed. To subscribe to the service, please put yourself on the list below. The format is: 3 spaces * Main.yourWikiName - yourEmailAddress

• EelcoDolstra - eelco@cs.uu.nl
• EelcoVisser - visser+Transform@cs.uu.nl
• MartinBravenboer - martin@cs.uu.nl
• ArieVanDeursen - Arie.van.Deursen@cwi.nl
• MikeVanEmmerik - emmerik+Transform@itee.uq.edu.au
• ChrisRussell - cdr@encapsule.com
• AndrewMalton - ajmalton@uwaterloo.ca

Related topics: TWikiUsers, TWikiRegistration

The following settings are web preferences of the TWiki.Sts web. These preferences overwrite the site-level preferences in TWikiPreferences, and can be overwritten by user preferences (your personal topic, i.e. TWikiGuest in the TWiki.Main web)

Preferences:

• Set WEBTITLE = Software Transformation Systems
• Set SHORTWEBTITLE = STS

• List of topics of the TWiki.Sts web:
  • Set WEBTOPICLIST =

• Web specific background color: (Pick a lighter one of the StandardColors)
  • Set WEBBGCOLOR = #EEEEAA

• Web specific background color: (Pick a lighter one of the StandardColors)
  • Set WEBCONTENTBGCOLOR = #EEEEAA

• List this web in the SiteMap:
  • If yes, Set SITEMAPLIST = on, and add the "what" and "use to..." description for the site map. Make sure to list only links that include the name of the web, e.g. Sts.Topic links.
  • Set SITEMAPLIST = on
  • Set SITEMAPWHAT = The Sofware Transformation Systems wiki
  • Set SITEMAPUSETO =

• Exclude web from a web="all" search: (Set to on for hidden webs)
  • Set NOSEARCHALL =

• Default template for new topics and form(s) for this web:
  • WebTopicEditTemplate^?: Default template for new topics in this web. (Site-level is used if topic does not exist)
  • TWiki.WebTopicEditTemplate: Site-level default template
  • TWikiForms: How to enable form(s)
  • Set WEBFORMS =

• Users or groups who are not / are allowed to view / change / rename topics in the Sts web: (See TWikiAccessControl)
  • Set DENYWEBVIEW =
  • Set ALLOWWEBVIEW =
  • Set DENYWEBCHANGE = TWikiGuest
  • Set ALLOWWEBCHANGE =
  • Set DENYWEBRENAME = TWikiGuest
  • Set ALLOWWEBRENAME =

• Users or groups allowed to change or rename this WebPreferences topic: (I.e. TWikiAdminGroup)
  • Set ALLOWTOPICCHANGE = TWikiAdminGroup
  • Set ALLOWTOPICRENAME = TWikiAdminGroup

• Web preferences that are not allowed to be overridden by user preferences:
  • Set FINALPREFERENCES = WEBTOPICLIST, DENYWEBVIEW, ALLOWWEBVIEW, DENYWEBCHANGE, ALLOWWEBCHANGE, DENYWEBRENAME, ALLOWWEBRENAME

Notes:

• A preference is defined as:
  6 spaces * Set NAME = value
  Example:
  • Set WEBBGCOLOR = #FFFFC0
• Preferences are used as TWikiVariables by enclosing the name in percent signs. Example:
  • When you write variable #EEEEAA , it gets expanded to #EEEEAA .
• The sequential order of the preference settings is significant. Define preferences that use other preferences first, i.e. set WEBCOPYRIGHT before WIKIWEBMASTER since =Copyright © 1999-2020 by the contributing authors.

All material on this collaboration platform is the property of the contributing authors.
Ideas, requests, problems regarding TWiki? Send feedback= uses the webmaster@strategoxt.org variable.

• You can introduce new preferences variables and use them in your topics and templates. There is no need to change the TWiki engine (Perl scripts).

Related Topics:

• TWikiPreferences has site-level preferences.
• TWikiUsers has a list of user topics. User topics can have optional user preferences.
• TWikiVariables has a list of common %VARIABLES%.
• TWikiAccessControl explains how to restrict access by users or groups.

/view/Sts program-transformation.org en-us Copyright 2020 by contributing authors Eelco Visser [webmaster@strategoxt.org] Eelco Visser [webmaster@strategoxt.org] TWiki TWiki.Sts /view/Sts /pub/TWiki/TWikiLogos/twikiRobot46x50.gif /view/Sts/SelfTracingProgramsUsingTXL?t=2008-11-02T21:33Z TXL solution to Chairmarks #4.3: Self-tracing program transformation. Main.JamesCordy 10 Oct 2005 File "TILtrace.Txl" Simple transform to make a Tiny Imperative ... (last changed by JamesCordy) 2008-11-02T21:33Z JamesCordy 1.2 updated major /rdiff/Sts/SelfTracingProgramsUsingTXL /rdiff/Sts/SelfTracingProgramsUsingTXL /view/Sts/STS08?t=2008-10-18T22:48Z STS'08: Software Transformation Systems Workshop (CANCELED) part of the Fifth international conference on Generative Programming and Component Engineering (GPCE'08 ... (last changed by YannisSmaragdakis) 2008-10-18T22:48Z YannisSmaragdakis 1.4 updated major /rdiff/Sts/STS08 /rdiff/Sts/STS08 /view/Sts/BlW?t=2008-01-30T05:37Z a1 a2 a3 a4 a5 a6 a7 (last changed by TWikiGuest) 2008-01-30T05:37Z guest 1.1 updated major /rdiff/Sts/BlW /rdiff/Sts/BlW /view/Sts/StatementFoldingUsingTXL?t=2008-01-04T03:53Z TXL solution to Chairmarks #3.5, Statement folding, recognizing and optimizing compile-time known if statements, and possibly while and for statements. Thie simple ... (last changed by JamesCordy) 2008-01-04T03:53Z JamesCordy 1.1 updated major /rdiff/Sts/StatementFoldingUsingTXL /rdiff/Sts/StatementFoldingUsingTXL /view/Sts/StrengthReductionUsingTXL?t=2008-01-03T15:14Z TXL solution to Chairmarks #3.3, Strength reduction, recognize opportunities to reduce multiplication by an iterator to iterative addition. Thie simple example demonstrates ... (last changed by JamesCordy) 2008-01-03T15:14Z JamesCordy 1.1 updated major /rdiff/Sts/StrengthReductionUsingTXL /rdiff/Sts/StrengthReductionUsingTXL /view/Sts/GotoEliminationUsingTXL?t=2008-01-03T04:46Z TXL solution to Chairmarks #2.5, Goto elimination, recognize and transform while-equivalent goto structures. Main.JamesCordy 31 Dec 2007 File "TILgotoelim.Txl" Goto ... (last changed by JamesCordy) 2008-01-03T04:46Z JamesCordy 1.2 updated major /rdiff/Sts/GotoEliminationUsingTXL /rdiff/Sts/GotoEliminationUsingTXL /view/Sts/ConstantFoldingUsingTXL?t=2008-01-03T04:46Z TXL solution to Chairmarks #3.4, Constant folding, recognize and resolve opportunities to fold constant expressions. Thie simple example demonstrates constant propagation ... (last changed by JamesCordy) 2008-01-03T04:46Z JamesCordy 1.1 updated major /rdiff/Sts/ConstantFoldingUsingTXL /rdiff/Sts/ConstantFoldingUsingTXL /view/Sts/CommonSubexpressionEliminationUsingTXL?t=2007-10-19T16:28Z TXL solution to Chairmarks #3.2, Common subexpression elimination. Thie simple example demonstrates the basics of common subexpression elimination at the statement ... (last changed by JamesCordy) 2007-10-19T16:28Z JamesCordy 1.1 updated major /rdiff/Sts/CommonSubexpressionEliminationUsingTXL /rdiff/Sts/CommonSubexpressionEliminationUsingTXL /view/Sts/ConsistentlyRenamedClonesUsingTXL?t=2007-10-16T01:15Z TXL solution to Chairmarks #4.6: Clone detection with consistent renaming. This example implements clone detection for clones of structured statements (if, while, ... (last changed by JamesCordy) 2007-10-16T01:15Z JamesCordy 1.1 updated major /rdiff/Sts/ConsistentlyRenamedClonesUsingTXL /rdiff/Sts/ConsistentlyRenamedClonesUsingTXL /view/Sts/ExactClonesUsingTXL?t=2007-10-16T00:31Z TXL solution to Chairmarks #4.6: Clone detection. This example implements clone detection for exact clones of structured statements (if, while, for) in a TIL program ... (last changed by JamesCordy) 2007-10-16T00:31Z JamesCordy 1.1 updated major /rdiff/Sts/ExactClonesUsingTXL /rdiff/Sts/ExactClonesUsingTXL /view/Sts/BackwardSlicingUsingTXL?t=2007-03-03T20:41Z TXL solution to Chairmarks #4.5: Static slicing. This example implements backward static slicing using cascaded markup to a fixed point. Notes: In an implementation ... (last changed by JamesCordy) 2007-03-03T20:41Z JamesCordy 1.3 updated major /rdiff/Sts/BackwardSlicingUsingTXL /rdiff/Sts/BackwardSlicingUsingTXL /view/Sts/STS06?t=2006-11-08T08:47Z STS'06: Software Transformation Systems Workshop part of the Fifth international conference on Generative Programming and Component Engineering (GPCE'06) October ... (last changed by EelcoVisser) 2006-11-08T08:47Z EelcoVisser 1.11 updated major /rdiff/Sts/STS06 /rdiff/Sts/STS06 /view/Sts/RemovingRedundantDeclarationsUsingTXL?t=2006-07-04T15:00Z TXL solution to Chairmarks #4.1: Removing redundant declarations. Main.JamesCordy 04 Jul 2006 File "TILredundant.Txl" TXL transformation to remove unused declarations ... (last changed by JamesCordy) 2006-07-04T15:00Z JamesCordy 1.1 updated major /rdiff/Sts/RemovingRedundantDeclarationsUsingTXL /rdiff/Sts/RemovingRedundantDeclarationsUsingTXL /view/Sts/MailingList?t=2006-06-03T07:59Z The sts mailinglist has been created following a discussion at the end of the STS workshop on Sunday October 24, 2004. General information about the mailing list is ... (last changed by MagneHaveraaen) 2006-06-03T07:59Z MagneHaveraaen 1.2 updated major /rdiff/Sts/MailingList /rdiff/Sts/MailingList /view/Sts/STS04?t=2006-02-06T14:45Z Software Transformation Systems Workshop 2004 STS04 was arranged Sunday, October 24th 2004 as part of Generative Programming and Component Engineering 2004 (GPCE'04 ... (last changed by MartinBravenboer) 2006-02-06T14:45Z MartinBravenboer 1.5 updated major /rdiff/Sts/STS04 /rdiff/Sts/STS04 /view/Sts/LiftInvariantAssignedComputationsUsingTXL?t=2005-11-04T22:26Z A more sophisticated TXL solution to Chairmarks #3.1, Move all invariant assigned computations outside of while loops. This is a more sophisticated version of Invariant ... (last changed by JamesCordy) 2005-11-04T22:26Z JamesCordy 1.1 updated major /rdiff/Sts/LiftInvariantAssignedComputationsUsingTXL /rdiff/Sts/LiftInvariantAssignedComputationsUsingTXL

• Simple search:

  Topic text (body)	All webs (not only TWiki.Sts web)
  Topic name	BookView

• Advanced search:

  Topic text (body)	Search	all Main TWiki Know Test web(s)
  Topic name	Sort by	Topic name Last modified time Last editor in reversed order

  
  

  Make search:	Case sensitive	RegularExpression search
  Don't show:	search string	summaries   total matches
  Do show:	BookView	topics (result count)

• Topic index: List of TWiki.Sts topics in alphabetical order.
  |All|A|B|C|D|E|F|G|H|I|J|K|L|M|N|O|P|Q|R|S|T|U|V|W|X|Y|Z|
  | All topics in BookView |

• Jump to topic: If you already know the name of the topic, enter the name of the topic at the second line of this page.

• WebChanges : Find out what topics in TWiki.Sts have changed recently.

• How to edit text:
  • Make changes to topics in GoodStyle,
  • Learn the TextFormattingRules, and
  • Have a look at the TextFormattingFAQ.

Statistics for TWiki.Sts Web

Month:	Topic Views:	Topic Saves:	Attachment Uploads:	Most Popular Topic Views:	Top Contributors for Topic Save and Uploads:
Feb 2008	2794	0	0	520 WebStatistics 280 WebHome 141 WebNews 122 WebRss 119 STS06 119 WebChanges 104 TILChairmarks 103 WebLeftBar  95 WebNotify  87 STS04  74 StsBench
Jan 2008	7892	14	0	1050 WebStatistics 884 WebHome 578 STS06 386 WebRss 323 WebChanges 293 WebNews 282 TILChairmarks 280 WebLeftBar 233 WebNotify 223 StsBench 217 STS04	14 JamesCordy
Dec 2007	5670	0	0	843 WebHome 655 WebStatistics 380 STS06 288 WebRss 234 WebChanges 212 WebNotify 195 WebLeftBar 186 WebNews 186 STS04 172 TILChairmarks 154 StsBench
Nov 2007	4467	1	0	734 WebStatistics 498 STS06 459 WebHome 173 WebNews 170 WebChanges 157 WebRss 156 STS04 148 WebNotify 118 TILChairmarks 115 StsBench 111 MailingList	1 JamesCordy
Oct 2007	5266	7	0	774 WebStatistics 557 STS06 498 WebHome 279 For-to-Nondeclaring-ForUsingTXL 228 WebNews 200 WebLeftBar 184 WebNotify 167 WebChanges 161 StsBench 148 STS04 145 TILChairmarks	7 JamesCordy
Sep 2007	7264	0	0	1077 WebStatistics 915 STS06 562 For-to-Nondeclaring-ForUsingTXL 507 WebHome 305 WebNews 250 WebChanges 232 StsBench 215 STS04 210 TILChairmarks 200 WebNotify 178 WebRss
Aug 2007	8339	0	0	1570 WebStatistics 1052 STS06 617 WebHome 571 For-to-Nondeclaring-ForUsingTXL 368 WebChanges 239 WebNews 219 WebNotify 204 WebLeftBar 193 TILChairmarks 189 StsBench 177 WebRss
Jul 2007	10762	0	0	1411 WebStatistics 1273 STS06 1124 WebHome 411 WebNews 404 WebChanges 344 WebLeftBar 310 WebNotify 304 STS04 266 For-to-Nondeclaring-ForUsingTXL 257 StsBench 250 TILChairmarks
Jun 2007	6118	1	0	745 STS06 605 WebHome 374 WebStatistics 271 STS04 247 WebChanges 220 WebNews 194 WebLeftBar 185 WebNotify 166 TILChairmarks 154 MailingList 153 StsBench	1 JamesCordy
May 2007	4509	0	0	678 STS06 670 WebStatistics 310 WebHome 169 STS04 164 WebChanges 159 WebNews 136 WebNotify 113 StsBench 112 WebLeftBar 110 WebRss 101 TILChairmarks
Apr 2007	4493	0	0	649 WebStatistics 435 WebHome 350 STS06 215 WebChanges 182 WebRss 159 WebNews 154 STS04 142 WebLeftBar 141 WebNotify 109 StsBench 105 TILChairmarks
Mar 2007	4927	8	0	704 STS06 549 WebStatistics 331 WebHome 226 TILChairmarks 201 WebRss 177 WebChanges 162 WebNews 159 STS04 142 WebLeftBar 131 WebNotify 130 StsBench	8 JamesCordy
Feb 2007	4562	0	0	605 WebStatistics 435 STS06 413 WebHome 316 WebRss 183 WebChanges 163 WebNews 140 WebLeftBar 139 STS04 137 StsBench 125 WebNotify 120 TILChairmarks
Jan 2007	5282	0	0	974 WebStatistics 521 WebHome 498 STS06 204 WebChanges 200 WebLeftBar 194 WebNews 181 WebRss 176 WebNotify 157 STS04 146 StsBench 106 TILChairmarks
Dec 2006	3769	0	0	408 WebHome 392 STS06 268 WebStatistics 180 WebNews 165 WebChanges 159 WebRss 146 WebLeftBar 134 StsBench 120 STS04 115 TILParserUsingTXL 113 WebNotify
Nov 2006	4060	1	1	554 WebRss 417 STS06 353 WebHome 353 WebStatistics 181 WebChanges 167 WebNews 131 STS04 111 StsBench 110 WebNotify 109 WebLeftBar  90 MailingList	2 EelcoVisser
Oct 2006	4108	13	11	584 STS06 454 WebStatistics 366 WebHome 363 WebRss 155 WebChanges 152 WebNews 131 STS04 124 WebLeftBar 113 WebNotify  93 StsBench  90 MailingList	24 EelcoVisser
Sep 2006	4278	9	0	715 WebRss 413 WebStatistics 329 WebHome 259 STS06 167 WebNews 155 WebChanges 146 WebLeftBar 145 WebNotify 114 STS04  98 TILChairmarks  97 TILParserUsingTXL	5 EelcoVisser   4 MagneHaveraaen
Aug 2006	6338	0	0	1117 WebStatistics 709 WebRss 551 WebHome 404 STS06 306 WebChanges 261 WebNotify 234 STS04 209 WebNews 186 WebLeftBar 147 StsBench 122 WebIndex
Jul 2006	7698	1	0	1282 WebStatistics 1056 WebHome 602 STS06 470 WebRss 362 WebNews 340 STS04 333 WebChanges 247 StsBench 237 WebNotify 185 WebLeftBar 180 TILChairmarks	1 JamesCordy
Jun 2006	7640	4	0	1333 WebStatistics 676 WebHome 646 STS06 636 WebRss 394 STS04 337 WebChanges 307 WebNews 279 WebNotify 192 StsBench 182 WebLeftBar 157 MailingList	4 MagneHaveraaen
May 2006	9640	12	0	2902 WebStatistics 789 WebHome 595 WebRss 472 WebChanges 438 STS04 379 WebNews 336 WebNotify 300 StsBench 224 WebLeftBar 201 WebSearch 187 WebIndex	9 EelcoVisser   2 MagneHaveraaen   1 JamesCordy
Apr 2006	6681	0	0	1065 WebStatistics 690 WebHome 383 STS04 361 WebChanges 261 WebNotify 248 WebNews 199 WebRss 176 WebSearch 172 StsBench 169 WebLeftBar 144 MailingList
Mar 2006	5627	0	0	1017 WebStatistics 611 WebHome 322 WebChanges 264 STS04 246 WebNotify 203 WebNews 191 WebRss 177 TILChairmarks 173 StsBench 144 WebIndex 143 WebChanges100
Feb 2006	3783	5	0	702 WebStatistics 488 WebHome 207 STS04 177 WebNotify 169 WebNews 163 WebChanges 142 WebRss 112 StsBench 110 WebLeftBar 102 TILChairmarks  79 TinyImperativeLanguage	5 MartinBravenboer
Jan 2006	3878	2	0	540 WebStatistics 510 WebHome 207 WebChanges 196 WebNotify 191 WebNews 186 STS04 130 StsBench 115 TILChairmarks 113 WebRss 111 WebLeftBar  95 WebIndex	2 EelcoVisser
Dec 2005	4384	0	0	694 WebHome 558 WebStatistics 251 WebNews 248 WebChanges 222 WebNotify 164 WebLeftBar 142 STS04 139 TILChairmarks 131 StsBench 128 WebSearch 108 WebIndex
Nov 2005	3211	13	0	515 WebHome 214 WebNotify 210 WebChanges 177 WebStatistics 165 WebNews 147 STS04 128 TILChairmarks 107 StsBench 103 WebIndex 100 WebLeftBar  95 WebSearch	13 JamesCordy
Oct 2005	3231	33	0	477 WebHome 261 WebStatistics 252 WebChanges 180 WebNews 168 STS04 160 WebNotify 132 StsBench 128 WebIndex 109 WebRss 109 WebLeftBar 106 TILChairmarks	33 JamesCordy
Sep 2005	1631	1	0	241 WebHome 125 WebStatistics 112 WebChanges 108 WebNotify  98 WebNews  69 StsBench  69 STS04  68 WebPreferences  66 WebSearch  60 TinyImperativeLanguage  58 WebIndex	1 JamesCordy
Aug 2005	2104	22	0	458 WebRss 344 WebHome 201 WebStatistics 141 WebChanges 109 WebNotify  89 STS04  79 StsBench  74 WebIndex  74 WebNews  69 WebLeftBar  52 TinyImperativeLanguage	22 JamesCordy
Jul 2005	1825	0	0	395 WebHome 136 STS04 119 WebNotify 116 WebChanges 102 StsBench  90 WebRss  86 WebNews  77 WebStatistics  66 WebIndex  58 WebSearch  52 WebChanges500
Jun 2005	1305	0	0	379 WebHome  86 WebChanges  75 WebNotify  73 StsBench  67 STS04  65 WebNews  63 WebRss  53 WebStatistics  44 WebIndex  40 TinyImperativeLanguage  40 WebChanges500
May 2005	1336	0	0	335 WebHome  91 WebChanges  90 STS04  82 WebRss  72 StsBench  71 WebNotify  58 WebNews  53 MailingList  51 WebIndex  49 WebSearch  48 WebStatistics
Apr 2005	1206	10	0	357 WebHome 105 WebChanges  68 STS04  59 WebPreferences  58 WebStatistics  56 WebNews  55 StsBench  53 TigerBenchmark  48 WebNotify  35 WebSearch  27 WebChanges500	5 JamesCordy   5 EelcoVisser
Mar 2005	1082	0	0	273 WebHome 242 WebChanges  61 STS04  54 WebPreferences  49 WebNews  44 WebStatistics  41 WebChanges100  40 StsBench  39 WebChanges200  36 WebChanges500  35 WebNotify
Feb 2005	966	0	0	285 WebHome  99 WebChanges  66 WebPreferences  65 WebNews  62 WebStatistics  47 WebNotify  42 STS04  38 StsBench  36 WebChanges200  33 WebContents?  30 WebSearch
Jan 2005	813	0	0	258 WebHome  83 WebChanges  66 WebNews  56 WebPreferences  39 StsBench  37 WebNotify  36 WebSearch  30 STS04  28 WebStatistics  27 WebContents?  19 WebIndex
Dec 2004	894	43	19	233 WebHome 134 STS04  71 WebChanges  68 WebNews  53 StsBench  53 WebPreferences  34 WebSearch  30 MailingList  26 WebNotify  23 WebStatistics  17 WebIndex	58 GaneshSittampalam   2 MartinBravenboer   2 EelcoVisser
Nov 2004	631	28	0	171 WebHome  98 StsBench  70 STS04  40 TigerBenchmark  35 WebChanges  24 WebNews  23 MailingList  18 WebPreferences  15 WebStatistics  15 WebSearch  15 WebContents?	15 EelcoVisser  11 JurgenVinju   2 GorelHedin

Notes:

• Do not edit this topic, it is updated automatically. (You can also force an update)
• TWikiDocumentation tells you how to enable the automatic updates of the statistics.
• Suggestion: You could archive this topic once a year and delete the previous year's statistics from the table.

Useful twiki things to do are:

• Keep track of WebChanges
• Get a WebNotify of changes
• Check the WebStatistics

• Browse the WebIndex
• Do a WebSearch

• See the other TWikiUsers
• Get your self a TWikiRegistration

• Set the WebPreferences
• Set the TWikiPreferences
• Set preferences for the left WebContents^?